package com.algorithm.sort;

import java.util.Arrays;

/**
 * @program: 计数排序
 * @author: luhd
 * @create: 2021-08-15
 */
public class CountSort {
    /**
     *  计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。
     *  作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
     */
    public static void main(String[] args) {
        int [] arr = {15,5,3,7,9 ,2,18,10,20,6};
        CountingSort(arr);
    }

    /**
     *  计数排序自我理解：新开辟一个数组，将待排序数组的值-最小值，，当作新数组的下标存储，，新数组的值，即为该数在待排序数组中的个数
     */
    public static int[] CountingSort(int[] arr){
        int len = arr.length;
        if(len == 0) return arr;
        int min = arr[0];
        int max = arr[0];
        for (int i = 0; i < len; i++) {
            if(arr[i]<min){
                min = arr[i];
            }
            if(arr[i]>max){
                max = arr[i];
            }
        }
        int[] bucket = new int[max - min +1];
        Arrays.fill(bucket,0);     //将数组的每一项赋值为0
        for (int i = 0; i < len; i++) {
            bucket[arr[i]-min]++;   //从bucket数组下标为0的开始存储数组的最小值，当数值有重复时，bucket++，即bucket的值表示出现的次数，数组下标+min为待排序数组的值
        }
        int[] result = new int[len];
        int index=0,k=0;
        while(index<len){       //避免使用if语句排序，
            if(bucket[k]>0){
                result[index] = k+min;
                bucket[k]--;
                index++;
            }else{
                k++;
            }
        }
        /*for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]+" ");
        }*/
        return result;
    }
}
